package com.sheng.leetcode.year2023.month06.day07;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/06/07
 * <p>
 * 2611. 老鼠和奶酪<p>
 * <p>
 * 有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。<p>
 * 下标为 i 处的奶酪被吃掉的得分为：<p>
 * 如果第一只老鼠吃掉，则得分为 reward1[i] 。<p>
 * 如果第二只老鼠吃掉，则得分为 reward2[i] 。<p>
 * 给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。<p>
 * 请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。<p>
 * <p>
 * 示例 1：<p>
 * 输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2<p>
 * 输出：15<p>
 * 解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。<p>
 * 总得分为 4 + 4 + 3 + 4 = 15 。<p>
 * 15 是最高得分。<p>
 * <p>
 * 示例 2：<p>
 * 输入：reward1 = [1,1], reward2 = [1,1], k = 2<p>
 * 输出：2<p>
 * 解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。<p>
 * 总得分为 1 + 1 = 2 。<p>
 * 2 是最高得分。<p>
 * <p>
 * 提示：<p>
 * 1 <= n == reward1.length == reward2.length <= 10^5<p>
 * 1 <= reward1[i], reward2[i] <= 1000<p>
 * 0 <= k <= n<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/mice-and-cheese">2611. 老鼠和奶酪</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2611 {

    @Test
    public void test01() {
//        int[] reward1 = {1, 1, 3, 4}, reward2 = {4, 4, 1, 1};
//        int[] reward1 = {1, 1}, reward2 = {1, 1};
//        int k = 2;
        int[] reward1 = {3, 3}, reward2 = {3, 5};
        int k = 1;
        System.out.println(new Solution().miceAndCheese(reward1, reward2, k));
    }
}

class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += reward2[i];
            // 将数组 reward1 中的元素减去 reward2，得到的值为将第二只老鼠吃的奶酪给第一只老鼠时的增加量
            reward1[i] -= reward2[i];
        }
        // 对增加量进行排序
        Arrays.sort(reward1);
        // 将增加量从大到小加 k 次即可
        for (int i = 0; i < k; i++) {
            ans += reward1[n - 1 - i];
        }
        return ans;
    }
}
